package main.java.indi.zyj.c150.dp;

import java.util.List;

public class _12_MinimumTotal {


    public int minimumTotal(List<List<Integer>> triangle) {


        int len = triangle.size();
        int[] dp = new int[len];

        dp[0] = triangle.get(0).get(0);

        for (int i = 1; i < len; i++) {
            // 左边界
            dp[i] = dp[i - 1] + triangle.get(i).get(i);
            // 中间二选一，选最小的
            for (int j = i - 1; j > 0 ; j--) {
                dp[j] = Math.min(dp[j - 1], dp[j]) + triangle.get(i).get(j);
            }
            // 右边界
            dp[0] += triangle.get(i).get(0);
        }
        // 最后一次遍历找最小的值
        int minTotal = dp[0];
        for (int i = 1; i < len; ++i) {
            minTotal = Math.min(minTotal, dp[i]);
        }
        return minTotal;

    }

}
